package com.yangzhe.algorithm.c027;

import java.util.PriorityQueue;

/**
 * 将数组和减半的最少操作次数
 * 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/
 */
public class Code03_MinimumOperationsToHalveArraySum_LeetCode {
	public static void main(String[] args) {
		int[] nums = {5,19,8,1};
		System.out.println(new Code03_MinimumOperationsToHalveArraySum_LeetCode().halveArray(nums));
	}

	/**
	 * 解法1：
	 * 1. 由于每次除以2要保留小数，所以使用Double
	 * 2. 使用大根堆，每次取堆顶的数除2，相当于每次都是取最大的数除2。除完后再放回去，这样就能得到最少的次数
	 */
	public int halveArray1(int[] nums) {
		int ans = 0;
		PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));

		Double sum = 0d;
		for(int i = 0; i < nums.length; i++) {
			heap.add((double)nums[i]);
			sum += nums[i];
		}

		Double targetSum = sum / 2;
		Double minusSum = 0d;
		while(minusSum < targetSum) {
			Double minus = heap.poll() / 2;
			heap.add(minus);
			minusSum += minus;
			ans++;
		}

		return ans;
	}

	public static int MAX_LENGTH = 100001;

	/**
	 * 大根堆
	 */
	public static long[] heap = new long[MAX_LENGTH];

	/**
	 * 解法2：
	 * 1. 优化大根堆，自己实现只要实现heapify，从底到顶建堆，复杂度只有O(n)
	 * 2. 数组中的数都(long)(num * 2 ^ 20) ，相当于这个数可以除20次2，而不会丢失精度，这样代替Double
	 */
	public int halveArray(int[] nums) {
		int ans = 0;
		if (nums.length == 0) {
			return 0;
		}
		long targetSum = 0;
		for(int i = 0; i < nums.length; i++) {
			heap[i] = (long)nums[i] << 20;
			targetSum += heap[i];
		}

		// 从底到顶建堆
		int size = nums.length;
		for (int i = size - 1; i >= 0; i--) {
			heapify(i, size);
		}

		targetSum = targetSum / 2;
		long minusSum = 0;
		while(minusSum < targetSum) {
			// 0位置就是堆顶
			long minus = heap[0] / 2;
			heap[0] = minus;
			heapify(0 , size);
			minusSum += minus;
			ans++;
		}

		return ans;

	}

	/**
	 * 大根堆，小的向下调整，和子节点中最大的那个交换
	 * 左儿子index = 2 * index + 1
	 * 右儿子index = 左儿子index + 1
	 */
	public void heapify(int index, int size) {
		int lIndex = 2 * index + 1;
		while (lIndex < size) {
			int bestIndex =  lIndex + 1 < size && heap[lIndex + 1] > heap[lIndex] ? lIndex + 1 : lIndex;
			if (heap[bestIndex] > heap[index]) {
				swap(bestIndex, index);
				index = bestIndex;
				lIndex = 2 * index + 1;
			} else {
				break;
			}
		}
	}

	public void swap(int a, int b) {
		long temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
	}

}
